package com.xufx.algorithm.dynamicplan;

/**
 * there is a robot on an m * n grid. The robot is initially located at the top-left corner(i.e grid[0][0]).
 * The robot tries to move to the bottom-right corner(i.e grid[m -1][n -1]). The Robot can only move either
 * down or right at any point in time.
 * Give the two integers m and n. return the number of possible unique paths that the robot can take to reach
 * the bottom-right corner.
 * THe test cases are generated so that the answer will be less than or equal to 2 *  ten to the nine
 *
 * case1: m = 3, n = 2 --> result = 3
 * case2: m = 3, n = 7 --> result = 28
 * case3: m = 3, n = 3 --> result = 6
 */

public class UniquePaths {
    public static void main(String[] args) {
        // DP
        int m = 3;
        int n = 7;
        System.out.println(unique(m ,n));
    }
    private static int unique(int m, int n){
        // DP --> Because this is type of sum
        // status: f[i][j] --> paths to this point
        // translation: f[i][j] = f[i -1][j] + f[i][j - 1]
        int[][] paths = new int[m][n];
        for(int i = 0; i <= m - 1; i++){
            for(int j = 0; j <= n - 1; j ++){
                if(i == 0 || j == 0){
                    paths[i][j] = 1;
                }else{
                    paths[i][j] = paths[i -1][j] + paths[i][j -1];
                }
            }
        }
        return paths[ m - 1][n - 1];
    }
}
